package search;

public class InsertionSearch {
    /**
     * 插值查找：二分查找的变种
     * mid=low+(high-low)*(key-a[low])/(a[high]-a[low])//(1/2)换为(key-a[low])/(a[high]-a[low])
     *
     *
     * 基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。
     * 当然，差值查找也属于有序查找。
     *
     * 对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。
     * 反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。
     *
     * @param a
     * @param value
     * @param n
     * @return
     */
    public static int InsertionSearch(int a[], int value, int n) {
        int low = 0;
        int high = n-1;
        int mid = 0;
        while (low <= high) {
            mid = low + (high-low) * (value-a[low]) / (a[high]-a[low]);
            if(a[mid] == value) {
                return mid;
            }
            if(a[mid] > value) {
                high = mid - 1;
            }
            else {
                low = mid + 1;
            }
        }
        return -1;
    }
}
